1. Field
Embodiments of the invention relate to the field of computer networking; and more specifically, to traffic shaping using sustained rate and constant rate emitter buckets.
2. Background
Traffic shaping attempts to control the volume and rate of data traffic, or traffic, being transmitted into a data network. The flow, of data in a network is typically occurs in bursts, meaning that the flow will be high at times, or low, and not always a constant rate of data. Traffic shaping counters these changes in rates by debursting traffic flows, i.e., smoothing high rate peaks and low rates troughs. The benefits of traffic shaping are lower latency, less jitter, and reduced packet loss.
Typically a network element situated at the edge of a network shapes the traffic, assuming the network element has the capability to do so. Traffic shaping is typically governed by a series of parameters that are taken from a customer's service level agreement. A service level agreement is an agreement between a network service provider and the customer that specifies, in measurable terms, what services and guarantees of service the network service provider provides for the customer. Service level guarantees typically involve different forms of rate guarantees. For example, one form of guarantees sets a long-term sustained transmission rate. This type of guarantee means that a customer can transmit over a long time frame up to the sustained transmission rate. Nevertheless, because of the bursty nature for data transmission, some service level agreements allow a customer to temporarily transmit traffic above the sustained transmission rate. The amount a customer can transmit above the sustained rate, also known as a burst, is characterized by an allowed burst rate and burst size. While in one embodiment, the burst rate is given in bytes per second and the burst size is given in bytes, in alternative embodiments, the rate and period can be given in different parameters (e.g., bits, kilobytes, megabytes, number of packets/cells/frames, milliseconds, microseconds, etc.).
A traffic shaper accumulates traffic by queuing received data packets in one or more packet queues. While in one embodiment there is one packet queue that holds all of the packets waiting to be transmitted by the traffic shaper, in alternate embodiments, there is a plurality of queues for different type of packets. In the alternate embodiments, packets can be classified into various unique streams of data using a variety of techniques known in the art, such as by destination address, source address, customer, application type, packet data contents, virtual local area network (VLAN) tag, multi-protocol label switching (MPLS) tag, type of service (TOS) bit, differentiated services (diffserv) bit, etc. Typically, a traffic shaper stores each of the unique streams of data in a separate queue while preparing to transmit the streams of data. By delaying or speeding up the transmission of queued packets, a traffic shaper shapes the incoming bursty traffic into a smooth flow of outgoing traffic. Furthermore, a traffic shaper can shape the separate streams of data differently and for independently (e.g., applying different sets of traffic shaping parameters to different stream of traffic, using separate queues for different streams of data, etc.). While in one embodiment, the traffic shaper shapes streams of Ethernet traffic, in alternate embodiments, the traffic shaper shapes the same and/or different types of traffic (e.g., Internet Protocol (IP), Asynchronous Transfer Mode (ATM), Frame Relay, Synchronous Optical Network (SONET), etc.)
Traffic shapers use the burst parameters to shape incoming bursty traffic. One of the general algorithms used for traffic shaping is the so-called token bucket algorithm. This algorithm dictates when traffic can be transmitted by using one or more token bucket that contains tokens. The tokens are, in effect, permissions for the traffic shaper to transmit certain number of bytes into the network. While in one embodiment, each token represents one or more bytes, in alternate implementations, a token can be used to represent one or more packets, cells, frames, or any other unit of measurement used in transmitting traffic. If there is a token in the bucket, the transmitting network element can transmit the data. In addition, the transmitting network element decrements the number of tokens corresponding to the traffic transmitted. On the other hand, if there are no tokens in the bucket (or not enough), the network element delays the transmission.
FIGS. 1-3, 5, 7, and 8 below use a number of common parameters, which are:
Bp: Burst size in bytes for the peak rate token bucket;
Rp: Rate in bytes per second for the peak rate token bucket;
Bs: Burst size in bytes for the sustained rate token bucket;
Rs: Rate in bytes per second for the sustained rate token bucket;
where Bs>=Bp and Rs<=Rp. Based on the above definitions, the following intermediate parameters are defined:
                    Tp        =                              (                          Bp              -              1                        )                    Rp                                    (        1        )                                BT        =                              (                          MBS              -              1                        )                    Rp                                    (        2        )                                Ts        =                              (                          MBS              -              1                        )                    *                      (                                          1                Rs                            -                              1                Rp                                      )                                              (        3        )            where Tp is the delay deviation tolerance for peak rate traffic. MBS is the maximum burst size in bytes traffic can be sent at peak rate, BT is the maximum burst time in which peak rate sending can last, and Ts is the delay deviation tolerance for sustained rate traffic. From traffic engineering,
                              Tp          +          Ts                =                              (                          Bs              -              1                        )                    Rs                                    (        4        )            
FIG. 1 is an illustration of a byte transmission graph 100 by a traffic shaper employing a sustained rate token bucket algorithm. In FIG. 1, graph 100 illustrates the time 106 when bytes 102 are transmitted by the traffic shaper. Superimposed on timeline 106 is when the traffic shaper transmits bytes 102 as illustrated by byte timeline 104. The token bucket in this example is characterized by a sustained rate Rs and a burst size Bs. This algorithm works by starting with a filled token bucket of depth size equal to the sustained burst size, Bs. For each byte(s) (or packet, cell, frame, etc.) transmitted, the traffic shaper decrements that token by the number of bytes transmitted. In addition, the traffic shaper slowly refills the token bucket at a rate equal to the Rs, the sustained rate. Thus, this algorithm allows for a traffic shaper to transmit at the linerate of the associated physical interface for the sustained burst size because there are initially enough tokens in the token bucket to support such a transmission burst.
FIG. 1 further illustrates nine bytes being evenly transmitted over time period 106 of 24,000 seconds with Rs=1/3000. Furthermore, FIG. 1 illustrates two typical scenarios. In one embodiment, if Bs=1, the traffic shaper starts working at time zero. In an alternate embodiment, if Bs>1, when having passed the initial burst based on Rs, the traffic shaper transmits in the sustained output period. The sustained output period can last as long as there is a byte to send (e.g., a packet is queued) when the traffic shaper is ready to transmit. In either embodiment, the same pattern repeats at time 27,000 seconds. The traffic shaper achieves the same sustained rate throughput over different lengths of time periods. While the embodiments illustrated by FIG. 1 show time period 106, alternate embodiments may have shorter or longer time periods, representing faster or slower sustained transmission rates.
On the other hand, FIG. 2 is an illustration of a byte transmission graph 200 by a traffic shaper employing a peak rate token bucket algorithm with Bp=4 and Rp=1/1000. FIG. 2 illustrates a typical scenario that generates the same throughput as the single sustained rate token bucket. To achieve this traffic pattern, additional limiting factor is needed. There are enough tokens in the sustained rate token bucket and there is no packet backlogged in the transmitted queue after time BT 210. In FIG. 2, graph 200 illustrates the time 206 when the traffic shaper transmits the bytes 202. Superimposed on timeline 206 is when the traffic shaper transmits bytes 202 as illustrated by byte timeline 204.
The peak rate token bucket is characterized by a peak rate Rp and burst size Bp. Similar to graph 100 in FIG. 1, graph 200 represents a traffic shaper transmitting a stream of data using token bucket algorithm configured with a depth of peak burst rate Bp and refills at a rate of Rp. The algorithm starts with a filled token bucket of depth Bp. For each packet transmitted by the traffic shaper, the token bucket is decremented by the size of the packet transmitted. In addition, the traffic shaper refills the token bucket at a rate of Rp. Similar to FIG. 1, this token bucket algorithm also allows the traffic shaper to initially transmit at the linerate of the associated physical interface for the peak burst size because there are initially enough tokens to support such a burst. Similar to FIG. 1, the same pattern repeats at time 27,000 second so that the same average throughput can be achieved over different length of observing time periods by both the pattern in FIG. 1 or FIG. 2. It should be aware that the single peak rate token bucket could continue its transmission at time 9,000 second. To achieve the traffic pattern as show in FIG. 2, the traffic may have had an interruption between the time 9,000 until 27,000, or a second limiting factor may be working together with the peak rate token bucket, such as the sustained rate token bucket described later. In comparison with graph 100, graph 200 illustrates a higher transmission rate because the bytes are transmitted is shorter time
A modification to further refine the burst is to use two independent token buckets. In this algorithm, four shaping parameters (Rp, Bp, Rs, and Bs) are used to define two independent token buckets applied in series. The first token bucket works as described above for the sustained rate single token bucket. The second token bucket typically enforces the burst traffic not to exceed a certain peak rate at a certain burst size.
FIG. 3 is an illustration of a byte transmission graph 300 by a traffic shaper utilizing a dual token bucket algorithm. Superimposed on timeline 306 is when the traffic shaper transmits bytes 302A-B as illustrated by byte timeline 304. This shaper uses two token buckets: a peak rate token bucket and a sustained rate token bucket. As above, each token bucket is independent, meaning that the adding and draining of tokens from the buckets is calculated independently. However, the draining of a token has to be done at the time both the buckets agree on. Because a token bucket always agrees to drain a token later than the earliest possible time, the bucket that decides the later draining time will govern the outgoing traffic pattern. Because this shaper uses both types of buckets, graph 300 shows a peak burst of bytes 302A and the sustained rate transmission of bytes 302B. The transmission of bytes 302A is governed by the peak rate token bucket whereas the transmission of bytes 302B is governed by the sustained rate token bucket. This is because during the time period BT-Tp, there are enough tokens in the sustained rate token bucket to support transmission of packets at a rate above Rs, but the number of tokens in the peak token bucket is being drained to zero. After time BT-Tp, the peak rate token bucket has more tokens and the sustained rate token bucket governs the transmission of bytes 302B. Superimposed on timeline 306 is when the traffic shaper transmits bytes 302A-B as illustrated by byte timeline 304. Furthermore, graph 300 illustrates Ts 312 and Tp 310.
FIG. 3 shows the scenario where the dual token bucket algorithm just starts working at time zero with both buckets full. It also assumes that there is always a byte available when the shaper decides to send a byte at its earliest possible time. Similar to FIGS. 1 and 2, transmission pattern 302B repeats beyond the right border of the figure to last for an infinite length time. When also considering the quiet period before time zero in which both buckets can fill up, the sustained rate throughput is achieved by byte transmission pattern 304 as in FIGS. 1 and 2. As per above, the peak rate token bucket when working together with a sustained rate token bucket allows burst traffic exceeding the sustained rate Rs but this algorithm fails to limit the traffic rate at the start of the burst period. This means that burst traffic can be transmitted at line rate at the beginning of the burst period.
Also known in the art are dual token bucket algorithms that couple the filling and draining of the token buckets together, instead of allowing the token bucket to be independent. Nonetheless, these algorithms still suffer the burstiness problems illustrated above.
FIG. 4 is a block diagram illustrating a dual token bucket traffic shaper. In FIG. 4, the traffic shaper with the dual token bucket algorithm 402 uses configuration 408 to shape the incoming unshaped traffic 404 and transmit the outgoing shaped traffic 406. Traffic shaper 402 uses the four configuration parameters, Rp, Bp, Rs, and Bs, to shape the traffic with a sustained rate and peak rate token bucket as described above.
While the token bucket algorithms smoothes out the traffic over long periods of time, all of these algorithms allow for short period bursts at linerate if there are enough tokens in the bucket. Even these short bursts can overwhelm other network elements down stream, especially when a high bandwidth device transmits short burst to lower bandwidth devices.